package src.week11.SHIYAN7.Demo4;

import java.util.Arrays;

public class Sorting1
{
    public static  String selectionSort(Comparable[] data) {
        int min;

        for (int index = 0; index < data.length - 1; index++) {
            min = index;
            for (int scan = index + 1; scan < data.length; scan++)
                if (data[scan].compareTo(data[min]) < 0 )
                    min = scan;

            swap(data, min, index);
        }
        return Arrays.toString(data);
    }

    private static  void swap(Comparable[] seed, int d1, int d2) {
        Comparable temp = seed[d1];
        seed[d1] = seed[d2];
        seed[d2] = temp;
    }
    public static void insertionSort(Comparable[] data) {
        for (int index = 1; index < data.length; index++) {
            Comparable key = data[index];
            int position = index;

            while (position > 0 && data[position - 1].compareTo(key) > 0) {
                data[position] = data[position - 1];
                position--;
            }
            data[position] = key;
        }
    }

    //冒泡排序
    public static void guluguluSort(Comparable[] data) {
        int position, scan;

        for (position = data.length - 1; position >= 0; position--) {
            for (scan = 0; scan <= position - 1; scan++)
                if (data[scan].compareTo(scan + 1) > 0)
                    swap(data, scan, scan + 1);
        }
    }

    //快速排序
    public static void QuickSort(Comparable[] data,int min,int max) {

        int pivot=0;
        if (min < max) {
            pivot = partition(data, min, max);
            QuickSort(data, min, pivot - 1);
            QuickSort(data, pivot + 1, max);
        }
    }

    private static int partition(Comparable[] data, int min, int max) {
        Comparable partitionValue = data[min];

        int left = min;
        int right = max;

        while (left < right) {
            while (data[left].compareTo(partitionValue) <= 0 && left < right)
                left++;
            while (data[right].compareTo(partitionValue) > 0)
                right--;
            if (left < right)
                swap(data, left, right);
        }
        swap(data, min, max);
        return right;
    }


    // 希尔排序
    public static void ShellSort(Comparable[] data, int length){
        int i = length;
        while (i > 1){
            // 动态定义间隔
            i = (i + 1) / 2;
            for (int j = 0;j < length - i;j++){
                if (data[j + i].compareTo(data[j])<0)
                {
                    Comparable temp = data[j + i];
                    data[j + i] = data[j];
                    data[j] = temp;
                }
            }
        }
    }


}
